// 38. Count and Say
// The count-and-say sequence is the sequence of integers beginning as follows:
// 1, 11, 21, 1211, 111221, ...

// 1 is read off as "one 1" or 11.
// 11 is read off as "two 1s" or 21.
// 21 is read off as "one 2, then one 1" or 1211.
// Given an integer n, generate the nth sequence.

// Note: The sequence of integers will be represented as a string.
package main

import (
	"strconv"
)

func countAndSay(n int) string {
	if n <= 0 {
		return ""
	}

	if n == 1 {
		return "1"
	}

	num, buf, count, tmp := make([]byte, 1, 2*n), make([]byte, 0, 2*n), int64(1), byte('1')
	num[0] = '1'

	for ; n > 1; n-- {
		tmp, count = num[0], 1
		for i, size := 1, len(num); i < size; i++ {
			if tmp == num[i] {
				count++
				continue
			}

			buf = strconv.AppendInt(buf, count, 10)
			buf = append(buf, tmp)
			tmp, count = num[i], 1
		}
		buf = strconv.AppendInt(buf, count, 10)
		buf = append(buf, tmp)

		num, buf = buf, num[:0]
	}
	return string(num)
}

func main() {
	num := countAndSay(1)
	r := "1"
	println(num, "=", r, num == r)

	num = countAndSay(2)
	r = "11"
	println(num, "=", r, num == r)

	num = countAndSay(3)
	r = "21"
	println(num, "=", r, num == r)

	num = countAndSay(4)
	r = "1211"
	println(num, "=", r, num == r)

	num = countAndSay(5)
	r = "111221"
	println(num, "=", r, num == r)
}
